class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> arr; // 大小代表最长长度，值代表这个长度的子序列的最后一个值
        arr.push_back(nums[0]);
        int n = nums.size();
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] > arr.back())
            {
                arr.push_back(nums[i]);
            }
            else // 二分找到要插入的位置
            {
                auto it = lower_bound(arr.begin(), arr.end(), nums[i]);
                if(it != arr.end()) // 第一个大于等于的位置
                    *it = nums[i];
            }
        }
        return arr.size();
    }
};